package AvlTree;

/**
 * @author ch
 */
public class AvlTree {
    public static void main(String[] args) {
        Node root1 = new Node(10);
        AvlTree tree = new AvlTree();
        root = root1;
        int[] nodes = {11,7,6,8,9};
        Node temp;
        for (int i = 0; i < nodes.length; i++) {
            temp = new Node(nodes[i]);
            tree.addNode(temp, root);
        }
        System.out.println("左子树的高度:"+root.getLeftHeight());
        System.out.println("右子树的高度:"+root.getRightHeight());
        System.out.println("树的高度:"+root.getHeight());
        preTravel(root);
    }

    /**
     * 从节点temp开始查找合适的位置插入节点node,一般为root,考虑到递归的原因起名,temp
     *
     * @param node 要添加的节点
     * @param temp 开始查找的节点
     */
    private static Node root;
    private void LLrotate(Node root){
        //左左旋转用于当添加下一个节点时,导致右子树与左子树的高度差大于一
        Node newNode= new Node(root.getValue());
        newNode.setLeft(root.getLeft());
        newNode.setRight(root.getRight().getLeft());
        root.setValue(root.getRight().getValue());
        root.setRight(root.getRight().getRight());
        root.setLeft(newNode);
    }
    private void RRrotate(Node root){
        Node node=new Node(root.getValue());
        node.setRight(root.getRight());
        node.setLeft(root.getLeft().getRight());
        root.setValue(root.getLeft().getValue());
        root.setLeft(root.getLeft().getLeft());
        root.setRight(node);
    }
    private void delNode(int value) {
        Node target = serarchTarget(value, root);
        if (target==null){
            return;
        }
        Node parent=searchParent(target,root);
        if (parent==null){
            //欲删除的结点,没有父亲节点(根节点)
            //根节点只有一个孩子
            if (root.getRight()!=null && root.getLeft()==null){
                root=root.getRight();
            }else if(root.getLeft()!=null && root.getRight()==null){
                root=root.getLeft();
            }else{
                //根节点不止一个孩子
                //默认提右节点
                Node temp=root;
                while(temp!=null){
                    if (temp.getRight()!=null){
                        temp.setValue(temp.getRight().getValue());
                        temp=temp.getRight();
                    }else if(temp.getLeft()!=null){
                        temp.setValue(temp.getLeft().getValue());
                        temp=temp.getLeft();
                    }else{
                        //到了叶子节点
                        Node tempP=serarchTarget(temp.getValue(),root);
                        if (tempP.getRight()!=null){
                            tempP.setRight(null);
                            temp=temp.getRight();
                        }else{
                            tempP.setLeft(null);
                            temp=temp.getLeft();
                        }
                    }
                }
            }
        }else {
            if (parent.getRight()==target){
                parent.setRight(null);
            }else{
                parent.setLeft(null);
            }
        }
    }
    /**
     * 根据提供的结点值,查找对应节点的父节点
     *
     * @param value
     * @return
     * @Param start 从start结点开始查找,一般都是root节点
     */
    private Node serarchTarget(int value, Node start) {
        if (start.getValue() == value) {
            return start;
        }
        if (value < start.getValue()) {
            if (start.getLeft() != null) {
                return serarchTarget(value, start.getLeft());
            } else {
                return null;
            }
        } else {
            if (start.getRight() != null) {
                return serarchTarget(value, start.getRight());
            } else {
                return null;
            }
        }
    }

    /**
     * 查找target节点的父节点
     *
     * @param target
     * @param start  开始查找的节点,一般为root
     * @return
     */
    private Node searchParent(Node target, Node start) {
        if (start.getRight() != null && start.getRight() == target
                || start.getLeft() != null && start.getLeft() == target) {
            return start;
        } else if (start.getRight() != null) {
            return searchParent(target, start.getRight());
        } else if (start.getLeft() != null) {
            return searchParent(target, start.getLeft());
        } else {
            return null;
        }
    }

    private void addNode(Node node, Node temp) {
        if (node.getValue() > temp.getValue()) {
            if (temp.getRight() == null) {
                temp.setRight(node);
            } else {
                addNode(node, temp.getRight());
            }
        } else {
            if (temp.getLeft() == null) {
                temp.setLeft(node);
            } else {
                addNode(node, temp.getLeft());
            }
        }
        if (root.getRightHeight()-root.getLeftHeight()>1){
            //右边高了,就要左左
           if(root.getRight()!=null && root.getRight().getLeftHeight()>root.getRight().getRightHeight()){
               RRrotate(root.getLeft());
           }
            LLrotate(root);

        }else if (root.getLeftHeight()-root.getRightHeight()>1){
            //左边高了
            if(root.getLeft()!=null && root.getLeft().getRightHeight()>root.getLeft().getLeftHeight()){
                LLrotate(root.getLeft());
            }
            RRrotate(root);
        }
    }

    private static void preTravel(Node root) {
        if (root == null) {
            return;
        }
        System.out.println(root.getValue());
        if (root.getLeft() != null) {
            preTravel(root.getLeft());
        }
        if (root.getRight() != null) {
            preTravel(root.getRight());
        }
    }
}

class Node {
    private int value;
    private Node left;
    private Node right;
    private int height;
    public Node() {
    }
    public Node(int value) {
        this.value = value;
    }
    public int getLeftHeight(){
        if (left==null){
            return 0;
        }
        return left.getHeight();
    }
    public int getRightHeight(){
        if (right==null){
            return 0;
        }
        return right.getHeight();
    }
    public int getHeight(){
        return  Math.max(left==null?0:left.getHeight(),right==null?0:right.getHeight())+1;
    }
    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    public void setRight(Node right) {
        this.right = right;
    }
}